﻿#define _CRT_SECURE_NO_WARNINGS 1
//题目：笨拙得手指
//奶牛贝茜正在学习如何在不同进制之间转换数字。
//但是她总是犯错误，因为她无法轻易的用两个前蹄握住笔。
//每当贝茜将数字转换为一个新的进制并写下结果时，她总是将其中的某一位数字写错。
//例如，如果她将数字 14转换为二进制数，那么正确的结果应为 1110，但她可能会写下 0110或 1111。
//贝茜不会额外添加或删除数字，但是可能会由于写错数字的原因，写下包含前导 0的数字。
//给定贝茜将数字 N转换为二进制数字以及三进制数字的结果，请确定 N的正确初始值（十进制表示）。
//输入格式
//第一行包含 N的二进制表示，其中一位是错误的。
//第二行包含 N的三进制表示，其中一位是错误的。
//输出格式
//输出正确的 N的值。
//数据范围
//0≤N≤109，且存在唯一解。
//输入样例：
//1010
//212
//输出样例：
//14
//样例解释
//14
//在二进制下的正确表示为 1110，在三进制下的正确表示为 112
//
//#include<iostream>
//#include<cstring>
//#include<algorithm>
//
//using namespace std;
//const int N = 100003;
//int h[N], ne[N], e[N], idx;
////手动模拟哈希表
//void insert(int x)
//{
//    int k = (x % N + N) % N;
//    e[idx] = x;
//    ne[idx] = h[k];
//    h[k] = idx++;
//}
//bool find(int x)
//{
//    int k = (x % N + N) % N;
//    for (int i = h[k]; i != -1; i = ne[i])
//    {
//        if (e[i] == x)
//        {
//            return true;
//        }
//    }
//    return false;
//}
////秦九韶算法换算成十进制
//int base(string q, int b)
//{
//    int res = 0;
//    for (int i = 0; i < q.size(); i++)
//    {
//        char str = q[i];
//        res = res * b + str - '0';
//    }
//    return res;
//}
//int main()
//{
//    string x, y;
//    memset(h, -1, sizeof h);
//    cin >> x >> y;
//    for (int i = 0; i < x.size(); i++)
//    {
//        string s = x;
//        s[i] ^= 1;
//        if (s.size() > 1 && s[0] == '0') continue;//若修改后第一位数字为0，那就是不存在得情况，当然是字符串长度大于1得情况，否则是符合
//        int n = base(s, 2);//将二进制转为十进制
//        insert(n);//将转为十进制得数字映射到哈希表
//    }
//    for (int i = 0; i < y.size(); i++)
//    {
//        for (int j = 0; j < 3; j++)
//        {
//            if (y[i] - '0' == j) continue;//如果相等等于没有修改，跳过本次循环
//            string s = y;
//            s[i] = j + '0';
//            if (s.size() > 1 && s[0] == '0') continue; //要注意坑，修改后得数字第一位为0得问题
//            int n = base(s, 3);//将三进制转为十进制
//            if (find(n))//看看哈希表有没有匹配得十进制 
//                cout << n << endl;
//        }
//    }
//    return 0;
//}



//题目：微博转发
//微博被称为中文版的 Twitter。
//微博上的用户既可能有很多关注者，也可能关注很多其他用户。
//因此，形成了一种基于这些关注关系的社交网络。
//当用户在微博上发布帖子时，他 / 她的所有关注者都可以查看并转发他 / 她的帖子，然后这些人的关注者可以对内容再次转发…
//现在给定一个社交网络，假设只考虑 L层关注者，请你计算某些用户的帖子的最大可能转发量。
//补充如果 B是 A的关注者，C是 B的关注者，那么 A的第一层关注者是 B，第二层关注者是 C。
//输入格式
//第一行包含两个整数，N表示用户数量，L表示需要考虑的关注者的层数。
//假设，所有的用户的编号为 1∼N。
//接下来 N行，每行包含一个用户的关注信息，格式如下：
//M[i] user_list[i]M[i] 是第 i名用户关注的总人数，user_list[i] 是第 i名用户关注的 M[i] 个用户的编号列表。
//最后一行首先包含一个整数 K，表示询问次数，然后包含 K个用户编号，表示询问这些人的帖子的最大可能转发量。
//输出格式
//按顺序，每行输出一个被询问人的帖子最大可能转发量。
//假设每名用户初次看到帖子时，都会转发帖子，只考虑 L层关注者。
//数据范围
//1≤N≤1000,1≤L≤6,1≤M[i]≤100,1≤K≤N
//输入样例：
//7 3
//3 2 3 4
//0
//2 5 6
//2 3 1
//2 3 4
//1 4
//1 5
//2 2 6
//输出样例：
//4
//5
//这里转化为图，如果A关注B，那么B连接A，因为B可以转发A的微博，如果有别的节点连接了B
//那么另外个节点可以转发B的微博，相当于转发了A的微博，这也是第二层关注
//#include<iostream>
//#include<algorithm>
//#include<queue>
//#include<cstring>
//using namespace std;
//const int N = 1010, M = 100010;//有1000个节点，10000条边
//int h[N], e[M], ne[M], idx;
//bool st[N];////判断该节点有无被访问
//int n, l;
//void add(int a, int b)
//{
//    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
//}
//int bfs(int x)
//{
//    queue<int>q;
//    memset(st, false, sizeof st);//每一次都要重置一次
//    q.push(x);
//    st[x] = true;
//    int res = 0;//记录最大转发量
//    for (int i = 0; i < l; i++)
//    {
//        int sz = q.size();//表示队列在某层中节点的个数
//        while (sz--)
//        {
//            auto t = q.front();
//            q.pop();
//            for (int j = h[t]; j != -1; j = ne[j])
//            {
//                int v = e[j];
//                if (!st[v])//表示节点有没有被访问过
//                {
//                    q.push(v);
//                    st[v] = true;
//                    res++;
//                }
//            }
//        }
//    }
//    return res;
//}
//int main()
//{
//    scanf("%d%d", &n, &l);
//    memset(h, -1, sizeof h);
//    for (int i = 1; i <= n; i++)
//    {
//        int cnt;
//        scanf("%d", &cnt);
//        while (cnt--)
//        {
//            int x;
//            scanf("%d", &x);
//            add(x, i);//i关注x，那么就从x连接i
//        }
//    }
//    int k;//表示k个询问
//    scanf("%d", &k);
//    for (int i = 1; i <= k; i++)
//    {
//        int x;//表示询问x的最大转发量
//        scanf("%d", &x);
//        printf("%d\n", bfs(x));
//    }
//    return 0;
//}


//题目：全球变暖
//你有一张某海域 N×N像素的照片，”.”表示海洋、”#”表示陆地，如下所示：
//.......
//.##....
//.##....
//....##.
//..####.
//...###.
//.......
//其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿，例如上图就有 2座岛屿。
//由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。
//具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
//例如上图中的海域未来会变成如下样子：
//.......
//.......
//.......
//.......
//....#..
//.......
//.......
//请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
//输入格式
//第一行包含一个整数N。以下 N行 N列，包含一个由字符”#”和”.”构成的 N×N字符矩阵，代表一张海域照片，”#”表示陆地，”.”表示海洋。
//照片保证第 1行、第 1列、第 N行、第 N列的像素都是海洋。
//输出格式
//一个整数表示答案。
//数据范围
//1≤N≤1000
//输入样例1：
//7
//.......
//.##....
//.##....
//....##.
//..####.
//...###.
//.......
//输出样例1：
//1
//输入样例2：
//9
//.........
//.##.##...
//.#####...
//.##.##...
//.........
//.##.#....
//.#.###...
//.#..#....
//.........
//输出样例2：
//1
//#include<iostream>
//#include<cstring>
//#include<algorithm>
//using namespace std;
//const int N = 1010;
//typedef pair<int, int>PII;
//PII q[N * N];//宽搜队列
//bool st[N][N];//记录陆地是否被遍历
//char g[N][N];//初始化地图
//int n;
//int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
//void bfs(int sx, int sy, int& total, int& bound)
//{
//    int hh = 0, tt = -1;
//    q[++tt] = { sx,sy };
//    st[sx][sy] = true;
//    while (hh <= tt)
//    {
//        PII t = q[hh++];
//        total++;
//        bool is_bound = false;
//        for (int i = 0; i < 4; i++)
//        {
//            int x = t.first + dx[i], y = t.second + dy[i];
//            if (st[x][y]) continue;//判断该岛屿有没有被遍历
//            if (g[x][y] == '.') //判断如果与大海相连，该陆地就会被淹没，并且跳出此次循环
//            {
//                is_bound = true;//被淹没就置为真
//                continue;
//            }
//            q[++tt] = { x,y };
//            st[x][y] = true;
//        }
//        if (is_bound) bound++;
//    }
//}
//int main()
//{
//    cin >> n;
//    for (int i = 0; i < n; i++)
//        scanf("%s", g[i]);
//    int cnt = 0;
//    for (int i = 0; i < n; i++)
//        for (int j = 0; j < n; j++)
//        {
//            if (!st[i][j] && g[i][j] == '#')
//            {
//                int total = 0, bound = 0;//total表示陆地连通数，bound表示海洋淹没陆地的数量
//                bfs(i, j, total, bound);
//                if (total == bound) cnt++;//如果岛屿数量和被淹没的数量一致，那么就代表一个岛屿被完全淹没
//            }
//        }
//    cout << cnt << endl;
//    return 0;
//}
